package com.example.summary.sort;

import com.alibaba.fastjson.JSON;


/**
 * Created by wzn on 2019/1/4.
 */
public class Quickly {

    static int[] x = {6, 11, 3, 9, 8};

    public static void main(String[] args) {
        s2(x, 0, x.length - 1);
        System.out.println(JSON.toJSONString(x));
    }

    public static void s(int[] array, int start, int end) {
        if (start < end) {
            int position = p(array, start, end);
            s(array, start, position - 1);
            s(array, position + 1, end);
        }
    }

    private static int p(int[] x, int start, int end) {
        int point = start - 1;
        int bijiao = x[end];

        for (int index = start; index <= end; index++) {
            if (x[index] <= bijiao) {
                point++;
                int temp = x[index];
                x[index] = x[point];
                x[point] = temp;
            }
        }
        return point;
    }


    public static void s2(int[] x, int start, int end) {
        if (start < end) {
            int mid = p2(x, start, end);
            s2(x, start, mid - 1);
            s2(x, mid + 1, end);
        }
    }

    private static int p2(int[] x, int start, int end) {
        int a = start-1;

        for (int i = start; i <= end; i++) {
            if (x[i] <= x[end]) {
                a++;
                int temp = x[i];
                x[i] = x[a];
                x[a] = temp;
            }

        }

        return a;
    }

}
